#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/**
 * File: Exercise1023.c
 * -------------------------------------------------------
 * 1.23 Modify your program from Exercise 1.22 to
 * plot the number of edges needed to connect N items, for $100\leq N \leq 1000$.
 * -------------------------------------------------------
 * 出处：[Exercise 1.22](https://gitcode.com/haoly1989/books/blob/main/AlgorithmsInC/exercises/chapter1/Exercise1022.c)
 * 
 */
int main(int argc, char **argv){
    srand((unsigned int)time(NULL));
    for (int k = 100; k < 1001; k++) {
        int N = k;
        int edges = 0;
        int setNum = N;
        int i, p, q, j;
        int id[N];
        int sz[N];

        //初始化id数组值为索引值
        for (i = 0; i < N; i++) {
            id[i] = i;
            sz[i] = 1;
        }

        int unionCount = 0;
        while (setNum > 1) {
            p = rand() % N;
            q = rand() % N;
            for (i = p; i != id[i]; i = id[i]) {
                id[i] = id[id[i]];
            }
            for (j = q; j != id[j]; j = id[j]) {
                id[j] = id[id[j]];
            }
            if (i == j) {
                continue;
            }
            if (sz[i] < sz[j]) {
                id[i] = j;
                sz[j] += sz[i];
            }else {
                id[j] = i;
                sz[i] += sz[j];
            }
            unionCount++;
            edges++;
            setNum--;
        }
        printf("connect %d items need total edges %d\n", N, edges);
    }
    return 0;
}